#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    bool fun(string str, string s) {
        int len1 = str.size();
        int len2 = s.size();
        int cnt = 0;
        if (len1 >= len2) {
            for (int i = len1 - len2; i < len1; i++) {
                if (str[i] != s[cnt++]) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }

    int numDecodings(string s) {
        int len = s.size();
        vector<int> dp(len + 1);
        dp[0] = 1;
        for (int i = 1; i <= len; i++) {
            string cur = s.substr(0, i);

            for (int j = 1; j <= 26; j++) {
                string res = to_string(j);
                if (res.size() > i)continue;
                if (fun(cur, res)) {
                    dp[i] += dp[i - res.size()];
                }
            }
        }
        return dp[len];
    }
};